Traffic on a telecommunications network is governed by data flows. A data flow is a transfer of data from a source node to a destination node. A destination node may be connected to a source node by one or more intermediate nodes. In some example embodiments, an intermediate node may be a router.
A given node may act as one of a source node, a destination node or an intermediate node in respect of a first flow and as a different one in respect of a second flow.
FIG. 1 shows an example fragment of a telecommunications network 100. The network 100 comprises a plurality of nodes 110 interconnected by links 120. For purposes of illustration, the nodes are shown in an array of 6 rows labelled A-F and 8 columns labelled 1-8, so that a given node may be referenced by a row and column reference. Those having ordinary skill will appreciate that while the network fragment is shown as a rectangular array of nodes 110, with links 120 between consecutive nodes in the same row and/or column, and are labelled in such fashion, the nodes 110 and the links 120 between them are not typically so aligned, nor are the nodes 110 typically so labelled.
Not every node 110 is directly connected to another node 110 by a link 120. For example, nodes A(D2) and B(C3) are not directly connected by a link 120. Rather, there are a plurality of paths between them, each comprising one or more links 120 to intermediate nodes. In the figure, two such paths A-C-B 131, A-D-B 132 are shown, each passing through a different intermediate node C(C2), D(D3). If nodes A and B are considered to be the source node and destination node respectively of a flow, then node C or D (depending upon which of the two paths 131, 132 is being considered), will be an intermediate node.
As is shown in FIG. 1, in connection with node A, a node that is a source node in respect of one flow can be a source node in respect of another flow, whether or not such flow has the same destination node. Similarly, as is shown in FIG. 1, in connection with node B, a node that is a destination node in respect of one flow can be a source node in respect of another flow, whether or not such flow has the same source node.
Further, a node that is an intermediate node in respect of one flow may be an intermediate node in respect of another flow, whether or not such flow has the same source or destination node. Still further, a node 110 that is a source node in respect of one flow may be a destination node or an intermediate node in respect of another flow. Moreover, a node 110 that is a destination node in respect of one flow may be a source node or an intermediate node in respect of another flow, and a node 110 that is an intermediate node in respect of one flow may be a source node or a destination node in respect of another flow.
Turning now to FIG. 2, there are shown nodes E(C3) and F(D6), with a number of paths 210, 220, 230, 240 between them. Each of the paths 210, 220, 230, 240 are of different length. Paths 210, 220, 230 as well as paths 210, 220, 240 do not pass through any common intermediate nodes and are each of a different length (measured by number of intermediate nodes). Path 240 shares common intermediate nodes with path 230, with the exception of node G(B7), which is used in path 230 to move from node B6 to C7, but not in path 240. Rather, path 240 moves from along a sub-path 241 fragment B6-A6-A7-A8-B8-C8-C7.
A given flow may become active at a point in time and be deactivated at another point in time. Between activation and deactivation of a flow, the amount that the flow is used gives rise to a load associated with the flow. The load of a flow may change over time. The total load of all flows passing through a given node is known as the network load for such node.
The network may support one or more services. Referring now to FIG. 3, there is shown a schematic view of a plurality of originating nodes and a plurality of destination nodes that may be associated with an example service. Each service tends to have associated with it a number of potential flows. In some cases, the flows associated with a given service may originate from one or more nodes 110, such as, by way of non-limiting illustration, nodes 311-314 and/or may terminate at one or more nodes 110, such as, by way of non-limiting illustration, nodes 321-323. By way of non-limiting example, the service may be a machine-type communication (MTC) service serving a utility, in which case, the originating nodes may be an MTC sensor or an access point (AP) to which such MTC sensor is connected, in a given geographic region and the destination nodes may be an AP or a point of presence (PoP) associated with a service provider to which the utility may be a subscriber. Thus, at any given time, there may be one or more flows from one or more of the originating nodes 311-314 to one or more of the destination nodes 321-323. The knowledge of about which flows are currently active or inactive is generally available, at least as a statistical concept.
Each such flow, when active, will follow a path from the originating node 311-314 to the destination node 321-323 associated therewith, with generally little or no restriction on what intermediate nodes will define such path.
Traffic engineering (TE) is a method of optimizing the performance of a network by dynamically analyzing, predicting and regulating the behaviour of data flows, whether or not associated with a given service, transmitted along the network 100. TE methods seek to minimize delay or data failure as the network load increases by changing the routing of flows through intermediate nodes subject to network constraints and in accordance with network performance objectives. Such routing changes are effected through control signalling, such as from a Software-Defined Network (SDN) Controller (SDN-C) to a router.
From time to time, the routing of flows may be altered or considered for alteration, by way of non-limiting example, because of change in demands of data flows. In such instances, TE is said to be triggered. The frequency of TE triggers may itself impact the overall performance of the network 100. If TE is only infrequently triggered, traffic bottlenecks may develop which may adversely impact network performance. On the other hand, by increasing the frequency of TE, the determination of whether or not to alter the routing of flows will increase. In some cases, such determination imposes a computational load that may adversely impact network performance. Potentially more significantly, a determination to alter the routing of flows consequent on a TE trigger will impose a control signalling load to effect the routing alteration itself.
Such tension may be managed by controlling the frequency and/or conditions that may trigger TE. A number of TE approaches have been employed. Some approaches can be categorized by the frequency of the TE triggers. Static TE involves a single initial global TE trigger, or in some cases, an infrequent (by way of non-limiting example, periodic) TE trigger. By contrast, dynamic TE is characterized by triggering TE trigger globally throughout the network 100 whenever a flow becomes active or is deactivated. This may be problematic if there are a lot of flow activations and/or deactivations, especially but not limited to services supporting MTC, since typically MTC services are characterized by a very large number of short-lived flows. Other scenarios that are characterized by a very high flow arrival rate may also result in a high frequency of TE triggers.
Semi-static TE represents a trade-off between the extremes of static and dynamic TE, in that a subset of circumstances is identified, the occurrence of one or more of which triggers a TE assessment.
Other TE approaches can be characterized by what happens when TE is triggered. Typically when TE is triggered, a path is selected for each active flow in the network, that is, a path between an originating node and a destination node, through zero or more intermediate nodes, is identified. Once the paths have been selected, routing changes are propagated to routers in the network through control plane signalling to give effect to the path changes so identified.
In some cases, path selection is computed at the time of the TE trigger. In some cases, path selection is pre-computed accessed at the time of the TE trigger. The advantage of pre-computing path selection is that the computational load in path selection is avoided at the time of the TE trigger. However, because path selection occurs a priori, the method of selecting the path typically does not take into account the prevailing network loading at the time of the TE trigger. This may limit the availability of a subset of path selection methods.
The most complete path selection method that could be taken is known as joint optimization of paths. In such action, when TE is triggered, every flow is considered, along with its associated network load to optimize paths of flows through intermediate nodes such that the overall network performance is optimized. For a given flow, this may mean that a longer path may be called for, to avoid a traffic bottleneck at a given intermediate node because of constraints imposed by one or more other flows.
By way of non-limiting illustration, in FIG. 2, if the flow under consideration extends from originating node E to destination node F, any of paths 210, 220, 230, 240 may be a suitable path for the flow to follow.
If however, there is a bottleneck imposed at node G because the node is inoperative, or because a flow (by way of non-limiting illustration, from originating node H(B8) to destination node G) cannot be re-routed away from node G, path 240 may be considered to be the optimal path for the flow from node E to node F, even if path 230 (and indeed paths 210, 220) is shorter (in terms of number of intermediate nodes).
However, joint optimization of paths has been identified as having a computational complexity of Non-deterministic Polynomial-time hard (NP-hard), assuming a fixed number of paths per flow. As such, it is not feasible to perform joint optimization of paths when TE is triggered.
Nor is it feasible to perform joint optimization of all paths on a pre-computation basis since joint optimization takes into account the prevailing network load, and this will not be known at the time of computation.
More simplified approaches to path selection are available. A very simple such approach is known as “shortest path”. The approach takes into account a cost associated with each link 120 in each path. In such an approach, each flow is defined by the path that has the lowest associated cost, that is, the sum of the cost of links 120 that make up the path. In an example situation, where all links 120 have a common cost, the shortest path will be the path that has the least number of links 120 for the flow.
By way of non-limiting illustration, in FIG. 2, if the flow under consideration extends from originating node E to destination node F, and all links 120 shown have a common cost, of the four paths shown 210, 220, 230, 240, path 210 will be chosen as the shortest path.
The simplicity of such an approach is rooted in the fact that the path selection of a given flow is independent of the number or nature of other active flows. Consequently, the shortest path approach does not depend upon the network loading, which may include performance bottlenecks at a node 110 and/or a link 120 (by way of non-limiting example, when a large number of flow paths share a common link 120). By way of non-limiting illustration, path 210 would still be chosen under the shortest path approach, even if node I(D5) posed a significant performance bottleneck due to network loading.
Because the shortest path approach is independent of network loading, TE triggers can be avoided and the path selection can be pre-computed and implemented at the outset.
Other simplified approaches include approaches based on column generation. Such approaches do take into account to some extent the existence and loading of other flows and as such may provide improved performance over the shortest path approach. However, column generation approaches are not suitable for pre-computation. Further, while simpler than the optimal joint path selection approach, column generation approaches exhibit worse performance than such approach.